Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Симплекс-метод розв’язку задач лінійного програмування
Лабораторна робота № 3, 4
з дисципліни
" Методи оптимізації та дослідження операцій"
Львів –2007
Лабораторна робота №3
Симплекс-метод розв’язку задач лінійного програмування
Мета роботи: набуття навиків розв’язку задачі лінійного програмування симплекс-методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel
Порядок роботи:
Заповнити початкову симплекс-таблицю задачі лінійного програмування згідно заданого варіанту.
Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям симплекс методу задачі лінійного програмування.
Знайти максимальне та мінімальне значення цільової функції та оптимальний розвязок.
Проінтерпретувати отримані результати для вихідної задачі.
Оформити звіт для захисту лабораторної роботи за зразком
назва роботи
мета роботи
порядок роботи
короткі теоретичні відомості
алгоритм розв’язку задачі
малюнки відповідних таблиць
аналіз отриманих результатів та висновки
Короткі теоретичні відомості
Симплекс-метод розв’язку задач лінійного програмування
Симлекс-метод, відомий також як метод послідовного покращення плану, дозволяє послідовно переходити від одного базисного розв’язку до другого, при тому так, що значення цільової функції зростають. У результаті, оптимальне розв’язок знаходиться за cкінчену кількість кроків. Алгоритми симплекс-методу дозволяють також встановити, чи може бути задача лінійного програмування розв’язаною, взагалі.
Методикою, яка найкраще піддається формалізації і алгоритмізації для реалізації на обчислювальній техніці, є метод симплекс-таблиць.
Основою для методу симплекс-таблиць є розширена матриця обмежень. Вона характеризується наявністю одиничної підматриці, а всі вільні члени додатні:
Ap = [A1, ..., An, e1, ..., em, A0]. (1)
До такого вигляду можна привести довільну початкову матрицю обмежень застосувавши відомі перетворення .
Тоді, алгоритм розв’язку задачі лінійного програмування (задачі максимізації) методом симплекс-таблиць складатиметься з наступних кроків:
1. Розрахувати і заповнити початкову таблицю з одиничним базисом у вигляді
C
c1
C2
c3
. . .
cj
. . .
cn
Bx
ai0
A1
A2
A3
. . .
Aj
. . .
An
c1
x1
a10
A11
a12
a13
. . .
a1j
. . .
a1n
c2
x2
a20
A21
a22
a23
. . .
a2j
. . .
a2n
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
ci
xi
ai0
Ai1
ai2
ai3
. . .
aij
. . .
ain
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
. . .
cm
xm
am0
Am1
am2
am3
. . .
amj
. . .
Amn
(
a00
A01
a02
a03
. . .
a0j
. . .
a0n
2. За направляючий вибирають стовпець Aj для якого
. (2)
3. Направляючий рядок Ai вибирається за умовою:
. (3)
4. Виконується крок симплекс-перетворення з направляючим елементом aij використовуючи співвідношення:
а) для елементів направляючого рядка
, l = 0, 1, ..., n; (4)
б) для елементів направляючого стовпця
; r = 1, 2, ..., m, при чому r ( i; ; (5)
в) для решти елементів матриці
, l ( j, r ( i. (6)
г) для елементів індексного рядка
, , l = 1, 2, ..., n. (7)
Правильність обчислень перевіряється за формулами
, . (8)
У стовпці Bx замінити xi на xj, а в стовпці C ci на cj.
5. Якщо, всі , l = 1, 2, ..., n, то новий базисний розв’язок , оптимальний. У протилежному випадку переходиться на крок 2 і виконується наступна ітерація.
6. Другий, третій і четвертий кроки повторюються до тих пір, доки одна з ітерацій не завершиться одним з двох результатів:
а) всі , l = 1, 2, ..., n. Умова оптимальності базису останньої таблиці;
б) знайдеться такий a0j = (j < 0, що всі елементи цього стовпця a0j ( 0, r = 1, 2, ..., m. Це ознака необмеженості цільової функції на множині допустимих розв’...
